skip to main content
article
Free Access

Whole program paths

Published:01 May 1999Publication History
Skip Abstract Section

Abstract

Whole program paths (WPP) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.

References

  1. 1 G. Ammons, T. Ball, and J. R. Larus, "Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling," in Proceedings of the SIGPLAN '97 Conference on Programming Language Design and Implementation. Las Vegas, NV, 1997, pp. 85-96. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. 2 G. Ammons and J. R. Larus, "Improving Data-flow Analysis with Path Profiles," in Proceedings of the SiGPLAN '98 Conference on Programming Language Design and Implementation. Montreal, Canada, 1998, pp. 72-84. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. 3 S. Andler, "Predicate Path Expressions," in Proceedings of the Sixth Annual A CM Symposium on Principles of Programming Languages. San Antonio, Texas, 1979, pp. 226-236. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. 4 B. S. Baker, "Parametefized Duplication in Strings: Algorithms and an Application to Software Maintenance," SIAM Journal of Computing, vol. 26, pp. 1343-I 362, 1995. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. 5 V. Bala, "Low Overhead Path Profiling," Hewlett Packard Labs 1996.Google ScholarGoogle Scholar
  6. 6 T. Ball and J. R. Larus, "Efficient Path Profiling," in Proceedings of the 29th Annual iEEEdACM International Symposium on Microarchitecture. Paris, France, 1996, pp. 46-57. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. 7 T. Ball, P. Mataga, and M. Sagiv, "Edge Profiling Versus Path Profiling: the Showdown," in Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. San Diego, CA, 1998, pp. 134- 148. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. 8 R. Bodik, R. Gupta, and M. L. Sofia, "Refining Data Flow Information using Infeasible Paths," in Proceedings of the A CM SIGSOFT Fifth Symposium on the Foundations of Software Engineering. Zurich, Switzerland, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. 9 I.-C. K. Chen, J. T. Coffey, and T. N. Mudge, "Analysis of Branch Prediction via Data Compression," in Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge, MA, 1996, pp. 128-137. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. 10 E. N. Clarke, E. A. Emerson, and A. P. Sistla, "Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications," A CM Transactions on Programming Languages and Systems, vol. 8, pp. 244-263, 1986. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. 11 J. A. Fisher, "Trace Scheduling: A Technique for Global Microeode Compaction," IEEE Transactions on Computers, vol. C-30, pp. 478-490, 1981.Google ScholarGoogle Scholar
  12. 12 J. A. Fisher, J. R. Ellis, J. C. Ruttenber g, and A. Nicolau, "Parallel Processing: A Smart Compiler and a Dumb Machine," in Proceedings of the A CM SiGPLAN '84 Symposium on Compiler Construction. Montreal, Canada, 1984, pp. 37-47. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. 13 J. Gray, "The Benchmark Handbook for Database and Transaction Processing Systems," in The Morgan Kaufmann Series in Data Management Systems, J. Gray, Ed., second ed. San Francisco: Morgan Kaufmann, 1993.Google ScholarGoogle Scholar
  14. 14 R. Gupta, D. A. Berson, and J. Z. Fang, "Path Profile Guided Partial Dead Code Elimination Using Predication," in Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT). San Francisco, CA, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. 15 Q. Jacobson, E. Rotenberg, and J. E. Smith, "Path-Based Next Trace Prediction," in Proceedings of the 30th Annual IEEE/ACM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. 16 J. R. Larus, "Abstract Execution: A Technique for Efficiently Tracing Programs," Software--Practice and Experience, vol. 20, pp. 1241-1258, 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. 17 J. R. Larus and E. Schnarr, "EEL: Machine-independent Executable Editing," in Proceedings of the SiGPLAN '95 Conference on Programming Language Design and Implementation. La Jolla, CA, 1995, pp. 291-300. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. 18 D. Melski and T. Reps, "Interprocedural Path Profiling," Computer Sciences Department, University of Wisconsin- Madison, Technical Report TR- 1382, September 1998.Google ScholarGoogle Scholar
  19. 19 D. Melski and T. Reps, "Interprocedural Path Profiling," in Proceedings of CC '99: 8th International Conference on Compiler Construction. Amsterdam, The Netherlands, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. 20 D. Mosberger and L. L. Peterson, "Making Paths Explicit in the Scout Operating System," in Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation (OSDI). Seattle, WA, 1996, pp. 153-167. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. 21 C. G. Nevill-Manning and I. H. Witten, "Compression and explanation using hierarchical grammars," The Computer Journal, vol. 40, pp. 103-116, 1997.Google ScholarGoogle ScholarCross RefCross Ref
  22. 22 C. G. Nevill-Manning and I. H. Witten, "Linear-time, incremental hierarchy inference for compression," in Proceedings of the Data Compression Conference (DCC '97). Snowbird, UT: iEEE Computer Society, 1997, pp. 3-1 I. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. 23 A. R. Pleszkun, "Techniques for Compressing Program Address Traces," in Proceedings of the 27th Annual IEEE/A CM International Symposium on Mi croarchitecture, 1994, pp. 32-40. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. 24 C. Pu, T. Autrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. Walpole, and K. Zhang, "Optimistic Incremental Specialization: Streamlining a Commercial Operating System," in Proceedings of the Fifteenth A CM Symposium on Operating System Principles. Copper Mountaint Resort, CO, 1995, pp. 314-324. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. 25 E. Rotenberg, S. Bennett, and J. E. Smith, "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching," in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture. Paris, France, ! 996, pp. 24-34. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. 26 E. Rotenberg, Q. Jacobson, Y. Sazeides, and J. Smith, "Trace Processors," in Proceedings of the 30th Annual iEEE/A CM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997, pp. 138-148. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. 27 A. Srivastava and A. Eustace, "ATOM A System for Building Customized Program Analysis Tools," in Proceedings of the SIGPLAN '94 Conference on Programming Language Design and Implementation. Orlando, FL, 1994, pp. 196-205. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. 28 C. Young, N. Gloy, and M. D. Smith, "A Comparative Analysis of Schemes for Correlated Branch Prediction," in Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995, pp. 276-286. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Whole program paths

          Recommendations

          Comments

          Login options

          Check if you have access through your login credentials or your institution to get full access on this article.

          Sign in

          Full Access

          • Published in

            cover image ACM SIGPLAN Notices
            ACM SIGPLAN Notices  Volume 34, Issue 5
            May 1999
            304 pages
            ISSN:0362-1340
            EISSN:1558-1160
            DOI:10.1145/301631
            Issue’s Table of Contents
            • cover image ACM Conferences
              PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation
              May 1999
              304 pages
              ISBN:1581130945
              DOI:10.1145/301618

            Copyright © 1999 ACM

            Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

            Publisher

            Association for Computing Machinery

            New York, NY, United States

            Publication History

            • Published: 1 May 1999

            Check for updates

            Qualifiers

            • article

          PDF Format

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader